package 贪心;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 受标签影响的最大值.java
 * @Description TODO
 * @createTime 2020年11月18日 21:12:00
 * 我们有一个项的集合，其中第 i 项的值为 values[i]，标签为 labels[i]。
 *
 * 我们从这些项中选出一个子集 S，这样一来：
 *
 * |S| <= num_wanted
 * 对于任意的标签 L，子集 S 中标签为 L 的项的数目总满足 <= use_limit。
 * 返回子集 S 的最大可能的 和。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
 * 输出：9
 * 解释：选出的子集是第一项，第三项和第五项。
 * 示例 2：
 *
 * 输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
 * 输出：12
 * 解释：选出的子集是第一项，第二项和第三项。
 *
 * 思路：每次选最大的 然后记录它的标签 依次取次大的 如果标签符合 就取 不符合就不取 直到去了num个
 * 总结 当两个数组互相对应的时候可以用 二维数组来对应
 * 相当于控制变量法 先考虑好一端  在对另一端进行选择
 *
 */
public class 受标签影响的最大值 {
    public static void main(String[] args) {
        Solution solution=new Solution();
        int i = solution.largestValsFromLabels(new int[]{2,6,3,6,5}, new int[]{1,1,2,1,1}, 3, 1);
        System.out.println(i);
    }
    static class Solution {
        //在value数组中最多选择num个元素 他们的标签相同的最大数量要小于limit
        //使得选出的元素和最大 也就是两个元素控制变量
        public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
        int[][] list=new int[values.length][2];
        for(int i=0;i<values.length;i++){
            list[i][0]=values[i];
            list[i][1]=labels[i];
        }
            Arrays.sort(list, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o2[0]-o1[0];
                }
            });

            HashMap<Integer,Integer> map=new HashMap<>();
            int res=0;
            for(int i=0;i<list.length;i++){
                if(num_wanted==0){
                    break;
                }
               map.put(list[i][1],map.getOrDefault(list[i][1],0)+1);
                if(map.get(list[i][1])<=use_limit){

                    res+=list[i][0];
                    num_wanted--;
                }
            }

            return res;
        }
    }
}
